package 剑指offer;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @description:
 * @author: ywk
 * @date: 2020-11-07
 */
public class 字典树的实现 {
    public static void main(String[] args) {
        System.out.println(trieU(new String[][]{{"1", "qwer"}, {"1", "qwe"}, {"3", "qwer"}, {"4", "q"},
                {"2", "qwer"}, {"3", "qwer"}, {"4", "q"}}));
    }
    /**
     * @param operators string字符串二维数组 the ops
     * @return string字符串一维数组
     */
    public static String[] trieU(String[][] operators) {
        List<String> result = new ArrayList<>();
        PriorityQueue<String> cache = new PriorityQueue<>((o1, o2) -> o1.compareToIgnoreCase(o2));
        // write code here
        for (int i = 0; i < operators.length; i++) {
            String[] operator = operators[i];
            String word = operator[1];
            switch (operator[0]) {
                case "1":
                    insert(word, cache);
                    break;
                case "2":
                    delete(word, cache);
                    break;
                case "3":
                    result.add(search(word, cache) ? "YES" : "NO");
                    break;
                case "4":
                    result.add(String.valueOf(prefixNumber(word, cache)));
                    break;
            }
        }
        String[] arr = new String[result.size()];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = result.get(i);
        }
        System.out.println(result);
        return arr;
    }
    public static void insert(String word ,PriorityQueue<String> cache) {
        cache.add(word);
    }

    public  static void delete(String word, PriorityQueue<String> cache) {
        if (cache.contains(word)) {
            Iterator<String> iterator = cache.iterator();
            while (iterator.hasNext()) {
                String next = iterator.next();
                if (next.equals(word)) {
                    iterator.remove();
                    break;
                }
            }
        }
    }

    public static boolean search(String word, PriorityQueue<String> cache) {
        return cache.contains(word);
    }

    public static int prefixNumber(String pre, PriorityQueue<String> cache) {
        int count = 0;
        Iterator<String> iterator = cache.iterator();
        while (iterator.hasNext()) {
            String next = iterator.next();
            if (next.contains(pre)) {
                count++;
            }
        }
        return count;

    }
}
